package com.fang.algorithm.zuo.basis;

/**
 * @author fanglingxiao
 * @version 1.0
 * @description TODO
 * @date 2022/6/30 10:52 上午
 **/
public class BitMap {
    private final long[] bits;

    public BitMap(int max) {
        // >> n 等于 / 2的n次方
        // 比如max=170 则long类型每一位是8个字节64位，则bitmap数组的大小为3
        bits = new long[(max + 64) >> 6];
    }

    public void add(int num) {
        // num >> 6 求在数组的哪个下标上
        // num & 63 = num % 64 因为不管是&64或者&63都是剔除7位以上的二进制数 01111101111111
        // 1L << (num & 63) 让1左移num存储的位置上
        // 通过|运算(有1则1)来填充
        bits[num >> 6] = bits[num >> 6] | (1L << (num & 63));
    }

    public void delete(int num) {
        // (1 << (num & 63)) 得到结果的位置数 0001000
        // ～取反操作 1110111
        // & 原来的位置数不变，结果的位置变为0（代表删除）
        bits[num >> 6] = bits[num >> 6] & ~(1L << (num & 63));
    }

    public boolean contains(int num) {
        //
        return (bits[num >> 6] & (1L << bits[num & 63])) != 0;
    }
}
